package myself.a010BinaryTreeRecursion;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/27
 * Time 22:04
 * Mail 739153436@qq.com
 */
public class MaxDistance {
    public static int maxDistance2(Node head) {
        return process(head).distance;
    }

    // 求二叉树中两个节点的最长距离
    public static Info process(Node random) {
        if (random == null) {
            return new Info(0, 0);
        }
        Info left = process(random.left);
        Info right = process(random.right);

        int height = Math.max(left.height, right.height) + 1;

        // 三种情况可能成为最大值
        int d1 = left.distance;
        int d2 = right.distance;
        int d3 = left.height + right.height + 1;

        int maxDistance = Math.max(d1, Math.max(d2, d3));

        return new Info(maxDistance, height);
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        public int distance;
        public int height;

        public Info(int distance, int height) {
            this.distance = distance;
            this.height = height;
        }
    }
}
